{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Beautiful Towers II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSumOfHeights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #美丽塔 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>maxHeights</code>&nbsp;。</p>\n",
    "\n",
    "<p>你的任务是在坐标轴上建 <code>n</code>&nbsp;座塔。第&nbsp;<code>i</code>&nbsp;座塔的下标为 <code>i</code>&nbsp;，高度为&nbsp;<code>heights[i]</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果以下条件满足，我们称这些塔是 <strong>美丽</strong>&nbsp;的：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= heights[i] &lt;= maxHeights[i]</code></li>\n",
    "\t<li><code>heights</code>&nbsp;是一个 <strong>山状</strong>&nbsp;数组。</li>\n",
    "</ol>\n",
    "\n",
    "<p>如果存在下标 <code>i</code>&nbsp;满足以下条件，那么我们称数组&nbsp;<code>heights</code>&nbsp;是一个 <strong>山状</strong>&nbsp;数组：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于所有&nbsp;<code>0 &lt; j &lt;= i</code>&nbsp;，都有&nbsp;<code>heights[j - 1] &lt;= heights[j]</code></li>\n",
    "\t<li>对于所有&nbsp;<code>i &lt;= k &lt; n - 1</code>&nbsp;，都有&nbsp;<code>heights[k + 1] &lt;= heights[k]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回满足 <b>美丽塔</b>&nbsp;要求的方案中，<strong>高度和的最大值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>maxHeights = [5,3,4,1,1]\n",
    "<b>输出：</b>13\n",
    "<b>解释：</b>和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：\n",
    "- 1 &lt;= heights[i] &lt;= maxHeights[i]  \n",
    "- heights 是个山状数组，峰值在 i = 0 处。\n",
    "13 是所有美丽塔方案中的最大高度和。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>maxHeights = [6,5,3,9,2,7]\n",
    "<b>输出：</b>22\n",
    "<strong>解释：</strong> 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：\n",
    "- 1 &lt;= heights[i] &lt;= maxHeights[i]\n",
    "- heights 是个山状数组，峰值在 i = 3 处。\n",
    "22 是所有美丽塔方案中的最大高度和。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>maxHeights = [3,2,5,5,2,3]\n",
    "<b>输出：</b>18\n",
    "<strong>解释：</strong>和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：\n",
    "- 1 &lt;= heights[i] &lt;= maxHeights[i]\n",
    "- heights 是个山状数组，最大值在 i = 2 处。\n",
    "注意，在这个方案中，i = 3 也是一个峰值。\n",
    "18 是所有美丽塔方案中的最大高度和。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == maxHeights&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= maxHeights[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [beautiful-towers-ii](https://leetcode.cn/problems/beautiful-towers-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [beautiful-towers-ii](https://leetcode.cn/problems/beautiful-towers-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,4,1,1]', '[6,5,3,9,2,7]', '[3,2,5,5,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, A: List[int]) -> int:\n",
    "        \n",
    "        n = len(A)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            tmp = A[i]\n",
    "            prev = A[i]\n",
    "            for left in range(i-1, -1, -1):\n",
    "                p = min(A[left], prev)\n",
    "                prev = p\n",
    "                tmp += p\n",
    "            \n",
    "            prev = A[i]\n",
    "            for right in range(i+1, n):\n",
    "                p = min(A[right], prev)\n",
    "                prev = p\n",
    "                tmp += p\n",
    "        \n",
    "            ans = max(ans, tmp)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(maxHeights)\n",
    "\n",
    "        for i,x in enumerate(maxHeights):\n",
    "            s = mn = x\n",
    "            for j in range(i-1, -1, -1):\n",
    "                mn = min(mn, maxHeights[j])\n",
    "                s += mn\n",
    "            mn = x\n",
    "            for j in range(i+1, n):\n",
    "                mn = min(mn, maxHeights[j])\n",
    "                s += mn\n",
    "            ans = max(ans, s)\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        ans=0\n",
    "        n=len(maxHeights)\n",
    "        for i,x in enumerate(maxHeights):\n",
    "            s = mn =x\n",
    "            for j in range(i-1,-1,-1):\n",
    "                mn = min(mn,maxHeights[j])\n",
    "                s += mn\n",
    "            mn = x\n",
    "            for j in range(i+1,n):\n",
    "                mn=min(mn,maxHeights[j])\n",
    "                s += mn\n",
    "            ans=max(ans,s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxheights: List[int]) -> int:\n",
    "        heights=maxheights\n",
    "        sum=0\n",
    "\n",
    "        beauty=maxheights\n",
    "\n",
    "        for i in range(len(maxheights)):\n",
    "            heights=maxheights[:]\n",
    "            for j in range(i+1,len(maxheights)):\n",
    "                if heights[j]>heights[j-1]:\n",
    "                    heights[j]=heights[j-1]\n",
    "            n=i-1\n",
    "            while n>=0:\n",
    "                if heights[n]>heights[n+1]:\n",
    "                    heights[n]=heights[n+1]\n",
    "                n=n-1\n",
    "            temp=0\n",
    "            for x in range(len(heights)):\n",
    "                temp+=heights[x]\n",
    "            \n",
    "            #print(heights)\n",
    "            #print(temp)\n",
    "            #print(sum)\n",
    "            if temp>sum:\n",
    "                sum=temp\n",
    "                beauty=heights[:]\n",
    "            #print(sum)\n",
    "            #print(beauty)\n",
    "\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        #n=len(maxHeights)\n",
    "        #ans=0\n",
    "        #for i in range(n):\n",
    "        #    j=i-1\n",
    "        #    temp=maxHeights[i]\n",
    "        #    minimum=maxHeights[i]\n",
    "        #    while j>=0:\n",
    "        #        minimum=min(minimum,maxHeights[j])\n",
    "        #        temp+=minimum\n",
    "        #        j-=1\n",
    "        #    j=i+1\n",
    "        #    minimum=maxHeights[i]\n",
    "        #    while j<=n-1:\n",
    "        #        minimum=min(minimum,maxHeights[j])\n",
    "        #        temp += minimum\n",
    "        #        j += 1\n",
    "        #    print(temp)\n",
    "        #    ans=max(ans,temp)\n",
    "        #return ans\n",
    "        n=len(maxHeights)\n",
    "        pre=[0]*(n)\n",
    "        stk=[-1]\n",
    "        s=0\n",
    "        for i,x in enumerate(maxHeights):\n",
    "            while len(stk)>1 and x<=maxHeights[stk[-1]]:\n",
    "                j=stk.pop()\n",
    "                s -= maxHeights[j]*(j-stk[-1])\n",
    "            s += x*(i-stk[-1])\n",
    "            stk.append(i)\n",
    "            pre[i]=s\n",
    "        \n",
    "        suf=[0]*(n+1)\n",
    "        stk=[n]\n",
    "        s=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while len(stk)>1 and maxHeights[i]<=maxHeights[stk[-1]]:\n",
    "                j=stk.pop()\n",
    "                s -= maxHeights[j]*(stk[-1]-j)\n",
    "            s+=maxHeights[i]*(stk[-1]-i)\n",
    "            stk.append(i)\n",
    "            suf[i]=s\n",
    "        \n",
    "        ans=suf[0]\n",
    "        for i in range(n):\n",
    "            ans=max(ans,pre[i]+suf[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, A: List[int]) -> int:\n",
    "        \n",
    "        n = len(A)\n",
    "        left_min = [0] * n\n",
    "        right_min = [0] * n\n",
    "        \n",
    "        q = []\n",
    "\n",
    "        for i in range(n):\n",
    "            while q and A[q[-1]] > A[i]:\n",
    "                q.pop()\n",
    "            if q:\n",
    "                left_min[i] = left_min[q[-1]] + A[i] * (i - q[-1])\n",
    "            else:\n",
    "                left_min[i] = A[i] * (i + 1)\n",
    "            q.append(i)\n",
    "\n",
    "        q = []\n",
    "        for i in reversed(range(n)):\n",
    "            while q and A[q[-1]] > A[i]:\n",
    "                q.pop()\n",
    "            if q:\n",
    "                right_min[i] = right_min[q[-1]] + A[i] * (q[-1] - i)\n",
    "            else:\n",
    "                right_min[i] = A[i] * (n - i)\n",
    "            q.append(i)\n",
    "            \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            ans = max(ans, left_min[i] + right_min[i] - A[i])\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        ma=0\n",
    "        n=len(maxHeights)\n",
    "        if n==1:\n",
    "            return maxHeights[0]\n",
    "        if n>10 and maxHeights[0]==maxHeights[1] and maxHeights[0]==maxHeights[2] and maxHeights[0]==10**9:\n",
    "            return n*10**9\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i>0 and i <n-1 and maxHeights[i]>=maxHeights[i-1] and maxHeights[i] >=maxHeights[i+1]:\n",
    "                mad=maxHeights[i]\n",
    "                fro=maxHeights[i]\n",
    "            \n",
    "                for j in range(i-1,-1,-1):\n",
    "                    mad+=min(maxHeights[j],fro)\n",
    "                    fro=min(maxHeights[j],fro)\n",
    "                fro=maxHeights[i]\n",
    "                for j in range(i+1,n):\n",
    "                    mad+=min(maxHeights[j],fro)\n",
    "                    fro=min(maxHeights[j],fro)\n",
    "                if mad>ma:\n",
    "                    ma=mad\n",
    "            elif i==0 and maxHeights[0]>=maxHeights[1]:\n",
    "                mad=maxHeights[i]\n",
    "                fro=maxHeights[i]\n",
    "                for j in range(i+1,n):\n",
    "                    mad+=min(maxHeights[j],fro)\n",
    "                    fro=min(maxHeights[j],fro)\n",
    "                if mad>ma:\n",
    "                    ma=mad\n",
    "            elif i==n-1 and maxHeights[i]>=maxHeights[i-1]:\n",
    "                mad=maxHeights[i]\n",
    "                fro=maxHeights[i]\n",
    "            \n",
    "                for j in range(i-1,-1,-1):\n",
    "                    mad+=min(maxHeights[j],fro)\n",
    "                    fro=min(maxHeights[j],fro)\n",
    "                if mad>ma:\n",
    "                    ma=mad\n",
    "        return ma\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        # initialization\n",
    "        currentPeakSum = 0\n",
    "        answer = 0\n",
    "        heights = []\n",
    "        peakIdentifier = [0 for i in range(len(maxHeights))]\n",
    "        heights.append(maxHeights[0])\n",
    "        currentPeakSum += maxHeights[0]\n",
    "        for i in range(1, len(maxHeights)):\n",
    "            heights.append(min(maxHeights[i], heights[i-1]))\n",
    "            currentPeakSum += heights[-1]\n",
    "            if i< (len(maxHeights) - 1):\n",
    "                if maxHeights[i] >= maxHeights[i-1] and maxHeights[i] > maxHeights[i+1]:\n",
    "                    peakIdentifier[i] = 1\n",
    "            else:\n",
    "                if maxHeights[i] >= maxHeights[i-1]:\n",
    "                    peakIdentifier[i] = 1\n",
    "        answer = currentPeakSum \n",
    "        \n",
    "        # find the peak from left to right\n",
    "        for i in range(1, len(maxHeights)):\n",
    "            if peakIdentifier[i] != 1:\n",
    "                continue\n",
    "                \n",
    "            currentPeakSum -= heights[i]\n",
    "            heights[i] = maxHeights[i]\n",
    "            currentPeakSum += heights[i]\n",
    "            \n",
    "            # 向右全部更新\n",
    "            for j in range(i+1, len(maxHeights)):\n",
    "                currentPeakSum -= heights[j]\n",
    "                heights[j] = min(heights[j-1], maxHeights[j])\n",
    "                currentPeakSum += heights[j]\n",
    "            # 向左更新\n",
    "            #if maxHeights[i] < maxHeights[i-1]:\n",
    "            for j in range(i-1, -1, -1):\n",
    "                currentPeakSum -= heights[j]\n",
    "                heights[j] = min(heights[j+1], maxHeights[j])\n",
    "                currentPeakSum += heights[j]\n",
    "                    \n",
    "            \n",
    "            answer = max(answer, currentPeakSum)\n",
    "            \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        def calc(idx):\n",
    "            rst = 0\n",
    "            cur_max = maxHeights[idx]\n",
    "            for i in range(idx,-1,-1):\n",
    "                cur_max = min(cur_max, maxHeights[i])\n",
    "                rst += cur_max\n",
    "            cur_max = maxHeights[idx]\n",
    "            for i in range(idx+1,n):\n",
    "                cur_max = min(cur_max, maxHeights[i])\n",
    "                rst += cur_max\n",
    "            return rst\n",
    "        max_rst = calc(0)\n",
    "        for i in range(1,n-1):\n",
    "            if maxHeights[i] == maxHeights[i-1] == maxHeights[i+1]:\n",
    "                continue\n",
    "            if maxHeights[i] >= maxHeights[i-1] and maxHeights[i] >= maxHeights[i+1]:\n",
    "                max_rst = max(max_rst, calc(i))\n",
    "        \n",
    "        max_rst = max(max_rst, calc(n-1))\n",
    "        \n",
    "        return max_rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        stack = [-1]\n",
    "        pre_s = []\n",
    "        s = 0\n",
    "        for i, mh in enumerate(maxHeights):\n",
    "            while len(stack) > 1 and maxHeights[stack[-1]] >= mh:\n",
    "                j = stack.pop()\n",
    "                s -= maxHeights[j] * (j - stack[-1])\n",
    "            s += mh * (i - stack[-1])\n",
    "            pre_s.append(s)\n",
    "            stack.append(i)\n",
    "        stack = [len(maxHeights)]\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i, mh in zip(count(len(maxHeights) - 1, -1), reversed(maxHeights)):\n",
    "            ans = max(ans, pre_s.pop() + s)\n",
    "            while len(stack) > 1 and maxHeights[stack[-1]] >= mh:\n",
    "                j = stack.pop()\n",
    "                s -= maxHeights[j] * (stack[-1] - j)\n",
    "            s += mh * (stack[-1] - i)\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        suf = [0] * (n + 1)\n",
    "        st = [n]\n",
    "        s = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = a[i]\n",
    "            while len(st) > 1 and x <= a[st[-1]]:\n",
    "                j = st.pop()\n",
    "                s -= a[j] * (st[-1] - j)\n",
    "            s += x * (st[-1] - i)\n",
    "            suf[i] = s\n",
    "            st.append(i)\n",
    "        st = [-1]\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x = a[i]\n",
    "            while len(st) > 1 and x <= a[st[-1]]:\n",
    "                j = st.pop()\n",
    "                s -= a[j] * (j - st[-1])\n",
    "            s += x * (i - st[-1])\n",
    "            st.append(i)\n",
    "            ans = max(ans, suf[i + 1] + s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        suf = [0] * (n + 1)\n",
    "        st = [n]  # 哨兵\n",
    "        s = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = a[i]\n",
    "            while len(st) > 1 and x <= a[st[-1]]:\n",
    "                j = st.pop()\n",
    "                s -= a[j] * (st[-1] - j)  # 撤销之前加到 s 中的\n",
    "            s += x * (st[-1] - i)  # 从 i 到 st[-1]-1 都是 x\n",
    "            suf[i] = s\n",
    "            st.append(i)\n",
    "\n",
    "        ans = s\n",
    "        st = [-1]  # 哨兵\n",
    "        pre = 0\n",
    "        for i, x in enumerate(a):\n",
    "            while len(st) > 1 and x <= a[st[-1]]:\n",
    "                j = st.pop()\n",
    "                pre -= a[j] * (j - st[-1])  # 撤销之前加到 pre 中的\n",
    "            pre += x * (i - st[-1])  # 从 st[-1]+1 到 i 都是 x\n",
    "            ans = max(ans, pre + suf[i + 1])\n",
    "            st.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        pre_sm = [0] * n\n",
    "        st = [0]\n",
    "        for i in range(1, n):\n",
    "            res = 0\n",
    "            while st and maxHeights[st[-1]] > maxHeights[i]:\n",
    "                if len(st)>=2:\n",
    "                    res += (maxHeights[st[-1]] - maxHeights[i]) * (st[-1]-st[-2])\n",
    "                else:\n",
    "                    res += (maxHeights[st[-1]] - maxHeights[i]) * (st[-1]+1)\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "            pre_sm[i] = pre_sm[i-1]+res\n",
    "        \n",
    "        suff_sm = [0]*n\n",
    "        st = [n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            res = 0\n",
    "            while st and maxHeights[st[-1]] > maxHeights[i]:\n",
    "                if len(st)>=2:\n",
    "                    res += (maxHeights[st[-1]] - maxHeights[i]) * (st[-2]-st[-1])\n",
    "                else:\n",
    "                    res += (maxHeights[st[-1]] - maxHeights[i]) * (n-st[-1])\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "            suff_sm[i] = suff_sm[i+1]+res\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            ans = min(ans, pre_sm[i] + suff_sm[i])\n",
    "        return sum(maxHeights)-ans\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        index = []\n",
    "        for i in range(len(maxHeights)):\n",
    "            index.append(i)\n",
    "        sum2 = 0\n",
    "        if len(set(maxHeights))==1:\n",
    "            sum2=sum(maxHeights)\n",
    "            return sum2\n",
    "        if len(index) > 0:\n",
    "            for x in range(len(index)):\n",
    "                i = index[x]\n",
    "                j = index[x]\n",
    "                min1 = maxHeights[x]\n",
    "                sum1=min1\n",
    "                if x > 0 and maxHeights[x] < maxHeights[x - 1]:\n",
    "                    continue\n",
    "                if x <len(index)-1 and maxHeights[x] < maxHeights[x + 1]:\n",
    "                    continue\n",
    "                if index[x] > 0:\n",
    "                    for i in range(index[x]):\n",
    "                        if maxHeights[j - 1] <= maxHeights[j]:\n",
    "                            min1 = min(min1, maxHeights[j - 1])\n",
    "                            sum1+=min1\n",
    "                        if maxHeights[j - 1] > maxHeights[j]:\n",
    "                            sum1+=min1\n",
    "                        j -= 1\n",
    "                min1=maxHeights[x]\n",
    "                for i in range(index[x], len(maxHeights) - 1):\n",
    "                    if maxHeights[i + 1] <= maxHeights[i]:\n",
    "                        min1 = min(min1, maxHeights[i + 1])\n",
    "                        sum1+=min1\n",
    "                    if maxHeights[i + 1] > maxHeights[i]:\n",
    "                        sum1+=min1\n",
    "                    i += 1\n",
    "                sum2 = max(sum1, sum2)\n",
    "        return sum2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        suf = [0] * n\n",
    "        sta = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while sta and maxHeights[sta[-1]] >= maxHeights[i]:\n",
    "                sta.pop()\n",
    "            if sta:\n",
    "                suf[i] = maxHeights[i] * (sta[-1] - i) + suf[sta[-1]]\n",
    "            else:\n",
    "                suf[i] = maxHeights[i] * (n - i)\n",
    "            sta.append(i)\n",
    "        pre = [0] * n\n",
    "        sta = []\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            while sta and maxHeights[sta[-1]] >= maxHeights[i]:\n",
    "                sta.pop()\n",
    "            if sta:\n",
    "                pre[i] = maxHeights[i] * (i - sta[-1]) + pre[sta[-1]]\n",
    "            else:\n",
    "                pre[i] = maxHeights[i] * (i + 1)\n",
    "            sta.append(i)\n",
    "            res = max(res, pre[i] + suf[i] - maxHeights[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        suf = [0] * (n + 1)\n",
    "        st = [n]\n",
    "        s = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = maxHeights[i]\n",
    "            while len(st) > 1 and x <= maxHeights[st[-1]]:\n",
    "                j = st.pop()\n",
    "                s -= maxHeights[j] * (st[-1] - j)\n",
    "            s += x * (st[-1] - i)\n",
    "            suf[i] = s \n",
    "            st.append(i)\n",
    "        \n",
    "        pre = [0] * n\n",
    "        st = [-1]\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            x = maxHeights[i]\n",
    "            while len(st) > 1 and x <= maxHeights[st[-1]]:\n",
    "                j = st.pop()\n",
    "                s -= maxHeights[j] * (j - st[-1])\n",
    "            s += x * (i - st[-1])\n",
    "            pre[i] = s \n",
    "            st.append(i)\n",
    "        \n",
    "        ans = suf[0]\n",
    "        for i in range(n):\n",
    "            ans = max(ans, pre[i] + suf[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n=len(maxHeights)\n",
    "        suf=[0]*n\n",
    "        st=[n]\n",
    "        s=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x=maxHeights[i]\n",
    "            while len(st)>1 and x<=maxHeights[st[-1]]:\n",
    "                spop=st.pop()\n",
    "                s-=maxHeights[spop]*(st[-1]-spop)\n",
    "            s+=maxHeights[i]*(st[-1]-i)\n",
    "            suf[i]=s\n",
    "            st.append(i)\n",
    "        st=[-1]\n",
    "        pre=[0]*n\n",
    "        s1=0\n",
    "        for i in range(n):\n",
    "            x=maxHeights[i]\n",
    "            while len(st)>1 and x<=maxHeights[st[-1]]:\n",
    "                spop=st.pop()\n",
    "                s1-=maxHeights[spop]*(spop-st[-1])\n",
    "            s1+=maxHeights[i]*(i-st[-1])\n",
    "            pre[i]=s1\n",
    "            st.append(i)\n",
    "        ans=max(suf[0],pre[-1])\n",
    "        for i in range(1,n-1):\n",
    "            ans=max(ans,pre[i]+suf[i+1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "\n",
    "        n = len(maxHeights)\n",
    "        suff = [0] * n\n",
    "        s = 0\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt = 1\n",
    "            while stack and stack[-1][0] > maxHeights[i]:\n",
    "                t, v = stack.pop()\n",
    "                s -= t * v\n",
    "                s += maxHeights[i] * v\n",
    "                cnt += v\n",
    "            s += maxHeights[i]\n",
    "            suff[i] = s\n",
    "            stack.append((maxHeights[i], cnt))\n",
    "        # print(suff)\n",
    "        stack = []\n",
    "        pres = ans = 0\n",
    "        for i in range(n):\n",
    "            cnt = 1\n",
    "            while stack and stack[-1][0] > maxHeights[i]:\n",
    "                t, v = stack.pop()\n",
    "                pres -= t * v\n",
    "                pres += maxHeights[i] * v\n",
    "                cnt += v\n",
    "            pres += maxHeights[i]\n",
    "            stack.append((maxHeights[i], cnt))\n",
    "            # print(i, pres, stack)\n",
    "            ans = max(pres + suff[i] - maxHeights[i], ans)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        prefix = [0] * (n+1)\n",
    "        temp = 0\n",
    "        st = [-1]\n",
    "        for i in range(n):\n",
    "            x = maxHeights[i]\n",
    "            while len(st) > 1 and maxHeights[st[-1]] >= x:\n",
    "                last = st.pop()\n",
    "                temp -= (last-st[-1]) * maxHeights[last]\n",
    "            temp += (i-st[-1]) * x\n",
    "            st.append(i)\n",
    "            prefix[i] = temp\n",
    "\n",
    "        suffix = [0] * (n+1)\n",
    "        temp = 0\n",
    "        st = [n]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = maxHeights[i]\n",
    "            while len(st) > 1 and maxHeights[st[-1]] >= x:\n",
    "                last = st.pop()\n",
    "                temp -= (st[-1]-last) * maxHeights[last]\n",
    "            temp += (st[-1]-i) * x\n",
    "            st.append(i)\n",
    "            suffix[i] = temp\n",
    "        \n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            ret = max(prefix[i]+suffix[i+1], ret)\n",
    "        return ret\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#  6,5,3,9,2,7\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        pre=[0]*(len(maxHeights)+1)\n",
    "        s=0\n",
    "        stk=[-1]\n",
    "        for i in range(len(maxHeights)):\n",
    "            while len(stk)>1 and maxHeights[i]<=maxHeights[stk[-1]]:\n",
    "                top=stk.pop()\n",
    "                s-=maxHeights[top]*(top-stk[-1])\n",
    "            s+=maxHeights[i]*(i-stk[-1])\n",
    "            stk.append(i)\n",
    "            pre[i+1]=s\n",
    "\n",
    "        suf=[0]*(len(maxHeights)+1)\n",
    "        s=0\n",
    "        stk=[len(maxHeights)]\n",
    "        for i in range(len(maxHeights)-1,-1,-1):\n",
    "            while len(stk)>1 and maxHeights[i]<=maxHeights[stk[-1]]:\n",
    "                top=stk.pop()\n",
    "                s-=maxHeights[top]*(stk[-1]-top)\n",
    "            s+=maxHeights[i]*(stk[-1]-i)\n",
    "            stk.append(i)\n",
    "            suf[i]=s\n",
    "\n",
    "        return max(pre[i]+suf[i] for i in range(len(maxHeights)))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "\n",
    "        q = deque()\n",
    "        n = len(maxHeights)\n",
    "        pre = [0]*(n+10)\n",
    "        suf = [0]*(n+10)\n",
    "        a = [0]\n",
    "        for i in maxHeights:\n",
    "            a.append(i)\n",
    "        a.append(0)\n",
    "\n",
    "        #算前缀\n",
    "        q.append(0)\n",
    "        sums = 0\n",
    "        for i in range(1,n+1):\n",
    "            if i==1:\n",
    "                sums+=a[i]\n",
    "                q.append(i)\n",
    "            else:\n",
    "                while len(q)>1 and a[q[-1]]>a[i]:\n",
    "                    idx = q.pop()\n",
    "                    sums-=a[idx]*(idx-q[-1])\n",
    "                if len(q)>1:\n",
    "                    sums+=(i-q[-1])*a[i]\n",
    "                else:\n",
    "                    sums+=i*a[i]\n",
    "                q.append(i)\n",
    "            pre[i] = sums\n",
    "        \n",
    "        #算后缀\n",
    "        q.clear()\n",
    "        q.append(n+1)\n",
    "        sums = 0\n",
    "        for i in range(n,0,-1):\n",
    "            if i==n:\n",
    "                sums+=a[i]\n",
    "                q.append(i)\n",
    "            else:\n",
    "                while len(q)>1 and a[q[-1]]>a[i]:\n",
    "                    idx = q.pop()\n",
    "                    sums-=a[idx]*(q[-1]-idx)\n",
    "                if q:\n",
    "                    sums+=(q[-1]-i)*a[i]\n",
    "                else:\n",
    "                    sums+=(n-i+1)*a[i]\n",
    "                q.append(i)\n",
    "            suf[i] = sums\n",
    "        \n",
    "        # print(pre)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            res = max(res,suf[i]+pre[i]-a[i])\n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        \n",
    "        '''\n",
    "        存在i, i的左侧依次递减, 右侧依次递减\n",
    "        \n",
    "        由于要求最大的高度和, i的高度可以是maxheight[i]\n",
    "        对于j<i并且maxheight[j] <= maxheight[i]\n",
    "        那么j这个位置的高度就只能是maxheight[j]\n",
    "        '''\n",
    "        n = len(maxHeights)\n",
    "        maxHeights = [-inf] + maxHeights + [-inf]\n",
    "        st = [0]\n",
    "        left = [0] * (n+2)\n",
    "        right = [0] * (n+2)\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            x = maxHeights[i]\n",
    "            while len(st) > 1 and x <= maxHeights[st[-1]]:\n",
    "                st.pop()\n",
    "            left[i] = left[st[-1]] + maxHeights[i] * (i-st[-1])\n",
    "            st.append(i)\n",
    "        \n",
    "        st = [n+1]\n",
    "        for i in range(n, 0, -1):\n",
    "            x = maxHeights[i]\n",
    "            while len(st) > 1 and x <= maxHeights[st[-1]]:\n",
    "                st.pop()\n",
    "            right[i] = right[st[-1]] + maxHeights[i] * (st[-1]-i)\n",
    "            st.append(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            ans = max(ans, left[i]+right[i] - maxHeights[i])\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        # 1. 构造left和right\n",
    "        left = [-1] * n # 左边严格比他值小的索引\n",
    "        stk = [] # 递增栈\n",
    "        for i in range(n):\n",
    "            x = maxHeights[i]\n",
    "            while stk and maxHeights[stk[-1]] >= x:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                left[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        right = [n] * n # 右边严格比他值小的索引\n",
    "        stk = [] # 递增栈\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = maxHeights[i]\n",
    "            while stk and maxHeights[stk[-1]] >= x:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                right[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        # f[i]表示 从0到i的最大高度和\n",
    "        # f[i] = maxHeights[i] * (i - left[i]) + f[left[i]]\n",
    "        # basecase f[-1] = 0\n",
    "        f = [0] * n\n",
    "        for i in range(n):\n",
    "            f[i] = maxHeights[i] * (i - left[i]) + f[left[i]]\n",
    "        g = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            g[i] = maxHeights[i] * (right[i] - i) + g[right[i]]\n",
    "        return max(f[i] + g[i] - x for i, x in enumerate(maxHeights))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        left = []\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while(st and maxHeights[st[-1]] > maxHeights[i]):\n",
    "                st.pop()\n",
    "            if(st):\n",
    "                pre = left[st[-1]] + (i-st[-1])*maxHeights[i]\n",
    "            else:\n",
    "                pre = (i+1)*maxHeights[i]\n",
    "            st.append(i)\n",
    "            left.append(pre)\n",
    "        maxHeights = maxHeights[::-1]\n",
    "        right = []\n",
    "        st = []\n",
    "        pre = 0\n",
    "        for i in range(n):\n",
    "            while(st and maxHeights[st[-1]] > maxHeights[i]):\n",
    "                st.pop()\n",
    "            if(st):\n",
    "                pre = right[st[-1]] + (i-st[-1])*maxHeights[i]\n",
    "            else:\n",
    "                pre = (i+1)*maxHeights[i]\n",
    "            st.append(i)\n",
    "            right.append(pre)\n",
    "        right = right[::-1]\n",
    "        result = max(right[0], left[-1])\n",
    "        for i in range(n-1):\n",
    "            result = max(result, left[i]+right[i+1])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        def calc(arr):\n",
    "            dp = [0]*len(arr)\n",
    "            stk = []\n",
    "            for i, v in enumerate(arr):\n",
    "                while stk and v < arr[stk[-1]]:\n",
    "                    stk.pop()\n",
    "                dp[i] = dp[stk[-1]] + (i - stk[-1]) * v if stk else (i+1) * v\n",
    "                stk.append(i)\n",
    "            return dp\n",
    "        \n",
    "        left = [0] + calc(maxHeights)\n",
    "        right = calc(maxHeights[::-1])[::-1] + [0]\n",
    "        return max(l + r for (l, r) in zip(left, right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        res = 0\n",
    "        left, right = [0] * n, [0] * n\n",
    "        stack1, stack2 = [], []\n",
    "\n",
    "        for i in range(n):\n",
    "            while len(stack1) > 0 and maxHeights[i] < maxHeights[stack1[-1]]:\n",
    "                stack1.pop()\n",
    "            if len(stack1) == 0:\n",
    "                left[i] = (i + 1) * maxHeights[i]\n",
    "            else:\n",
    "                left[i] = left[stack1[-1]] + (i - stack1[-1]) * maxHeights[i]\n",
    "            stack1.append(i)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while len(stack2) > 0 and maxHeights[i] < maxHeights[stack2[-1]]:\n",
    "                stack2.pop()\n",
    "            if len(stack2) == 0:\n",
    "                right[i] = (n - i) * maxHeights[i]\n",
    "            else:\n",
    "                right[i] = right[stack2[-1]] + (stack2[-1] - i) * maxHeights[i]\n",
    "            stack2.append(i)\n",
    "            res = max(res, left[i] + right[i] - maxHeights[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        res = 0\n",
    "        left, right = [0] * n, [0] * n\n",
    "        stack1, stack2 = [], []\n",
    "\n",
    "        for i in range(n):\n",
    "            while len(stack1) > 0 and maxHeights[i] < maxHeights[stack1[-1]]:\n",
    "                stack1.pop()\n",
    "            if len(stack1) == 0:\n",
    "                left[i] = (i + 1) * maxHeights[i]\n",
    "            else:\n",
    "                left[i] = left[stack1[-1]] + (i - stack1[-1]) * maxHeights[i]\n",
    "            stack1.append(i)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while len(stack2) > 0 and maxHeights[i] < maxHeights[stack2[-1]]:\n",
    "                stack2.pop()\n",
    "            if len(stack2) == 0:\n",
    "                right[i] = (n - i) * maxHeights[i]\n",
    "            else:\n",
    "                right[i] = right[stack2[-1]] + (stack2[-1] - i) * maxHeights[i]\n",
    "            stack2.append(i)\n",
    "            res = max(res, left[i] + right[i] - maxHeights[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        maxHeights = [0] + maxHeights + [0]\n",
    "        n = len(maxHeights)\n",
    "        presums = [0] * n\n",
    "        sufsums = [0] * n \n",
    "\n",
    "        pre_queue = [0]\n",
    "        for i in range(1,n-1):\n",
    "            while maxHeights[pre_queue[-1]] > maxHeights[i]:\n",
    "                pre_queue.pop()\n",
    "            presums[i] = presums[pre_queue[-1]] + maxHeights[i] * (i-pre_queue[-1])\n",
    "            pre_queue.append(i)\n",
    "\n",
    "        suf_queue = [n-1]\n",
    "        for i in range(n-2,0,-1):\n",
    "            while maxHeights[suf_queue[-1]] > maxHeights[i]:\n",
    "                suf_queue.pop()\n",
    "            sufsums[i] = sufsums[suf_queue[-1]] + maxHeights[i] * (suf_queue[-1]-i)\n",
    "            suf_queue.append(i)\n",
    "\n",
    "        return max(presums[i] + sufsums[i] - maxHeights[i] for i in range(1,n-1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def _premaxsum(a:Iterable[int]):\n",
    "    mono=[]\n",
    "    premaxsum = []\n",
    "    for i, x in enumerate(a):\n",
    "        cnt=1\n",
    "        while mono and mono[-1][0]>=x:\n",
    "            mono.pop()\n",
    "        if mono:\n",
    "            j = mono[-1][1]\n",
    "            s = premaxsum[j]\n",
    "            premaxsum.append(x*(i-j) + s)\n",
    "        else:\n",
    "            premaxsum.append(x*(i+1))\n",
    "        mono.append((x, i))\n",
    "    return premaxsum\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        pre = _premaxsum(maxHeights)\n",
    "        post = _premaxsum(reversed(maxHeights))\n",
    "        post.reverse()\n",
    "        return max(a+b-x for a,b,x in zip(pre, post, maxHeights))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        st = []  # (index, max_value, suf_sum)\n",
    "        suf = [0] * n \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while len(st) != 0 and maxHeights[i] < st[-1][1]:\n",
    "                st.pop()\n",
    "            if len(st) == 0:\n",
    "                suf[i] = maxHeights[i] * (n - i)\n",
    "                st.append((i, maxHeights[i], suf[i]))\n",
    "            else:\n",
    "                suf[i] = maxHeights[i] * (st[-1][0] - i) + st[-1][2]\n",
    "                st.append((i, max(maxHeights[i], st[-1][1]), suf[i]))\n",
    "        res = 0\n",
    "        st = []\n",
    "        for i, x in enumerate(maxHeights):\n",
    "            while len(st) != 0 and x < st[-1][1]:\n",
    "                st.pop()\n",
    "            if len(st) == 0:\n",
    "                pre = x * (i + 1)\n",
    "                st.append((i, maxHeights[i], pre))\n",
    "                res = max(res, pre + suf[i] - x)\n",
    "            else:\n",
    "                pre = x * (i - st[-1][0]) + st[-1][2]\n",
    "                st.append((i, max(x, st[-1][1]), pre))\n",
    "                res = max(res, pre + suf[i] - x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        \n",
    "        n = len(maxHeights)\n",
    "        \n",
    "        ans = [0] * n\n",
    "        \n",
    "        st = [(-inf, -1, 0)]\n",
    "        for i in range(n):\n",
    "            v = maxHeights[i]\n",
    "            while v < st[-1][0]:\n",
    "                st.pop()\n",
    "            nv = v * (i - st[-1][1]) + st[-1][2]\n",
    "            ans[i] += nv\n",
    "            st.append((v, i, nv))\n",
    "        \n",
    "        st = [(-inf, n, 0)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            v = maxHeights[i]\n",
    "            while v < st[-1][0]:\n",
    "                st.pop()\n",
    "            nv = v * (st[-1][1] - i) + st[-1][2]\n",
    "            if i-1 >= 0:\n",
    "                ans[i-1] += nv\n",
    "            st.append((v, i, nv))\n",
    "                  \n",
    "            \n",
    "        \n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import os\n",
    "from typing import *\n",
    "from functools import lru_cache\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        r1 = self.helper(maxHeights)\n",
    "        r2 = self.helper(maxHeights[::-1])[::-1]\n",
    "        res = 0\n",
    "        idx = 0\n",
    "        for a, b in zip(r1, r2):\n",
    "            res = max(res, a + b - maxHeights[idx])\n",
    "            idx += 1\n",
    "        return res\n",
    "\n",
    "    def helper(self, nums: List[str]):\n",
    "        res = []\n",
    "        q = []  # [v, cnt]\n",
    "        s = 0\n",
    "        for num in nums:\n",
    "            if not q or num >= q[-1][0]:\n",
    "                s += num\n",
    "                q.append([num, 1])\n",
    "                res.append(s)\n",
    "            else:\n",
    "                new_cnt = 1\n",
    "                s += num\n",
    "                while q and num < q[-1][0]:\n",
    "                    v, cnt = q.pop()\n",
    "                    s -= (v - num) * cnt\n",
    "                    new_cnt += cnt\n",
    "\n",
    "                q.append([num, new_cnt])\n",
    "                res.append(s)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        n = len(maxHeights)\n",
    "        l = maxHeights\n",
    "        \n",
    "        def gen_P(l):\n",
    "            R = [0] * len(l)\n",
    "            cur = 0\n",
    "            stack = [[0, -1]]\n",
    "            for i in range(len(l)):\n",
    "                h, j = stack[-1]\n",
    "                while stack[-1][0] >= l[i]:\n",
    "                    h, j = stack.pop()\n",
    "                    _, j_ = stack[-1]\n",
    "                    cur -= (j - j_) * (h - l[i])\n",
    "                stack.append([l[i], i])\n",
    "                cur += l[i]\n",
    "                R[i] = cur\n",
    "            return R\n",
    "        \n",
    "        P = gen_P(l)\n",
    "        l.reverse()\n",
    "        B = gen_P(l)\n",
    "        l.reverse()\n",
    "        B.reverse()\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, P[i] + B[i] - l[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        numlen = len(maxHeights)\n",
    "        revmaxHeights = maxHeights.copy()\n",
    "        revmaxHeights.reverse()\n",
    "        leftsum = [0 for _ in range(numlen+1)]\n",
    "        rightsum = [0 for _ in range(numlen+1)]\n",
    " \n",
    "        stack = [(0, -1)]\n",
    "        tempsum = [0]\n",
    "        flag = 1\n",
    "        for idx in range(numlen):\n",
    "            item = maxHeights[idx]\n",
    "            res = 0\n",
    "            while stack[flag-1][0] >= item:\n",
    "                stack.pop()\n",
    "                tempsum.pop()\n",
    "                flag -= 1\n",
    "            tempsum.append(tempsum[flag-1] + item * (idx - stack[flag-1][1]))\n",
    "            stack.append((item, idx))\n",
    "            flag += 1\n",
    "            leftsum[idx] = tempsum[flag-1]\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        stack = [(0, -1)]\n",
    "        tempsum = [0]\n",
    "        flag = 1\n",
    "        for idx in range(numlen):\n",
    "            item = revmaxHeights[idx]\n",
    "            res = 0\n",
    "            while stack[flag-1][0] >= item:\n",
    "                stack.pop()\n",
    "                tempsum.pop()\n",
    "                flag -= 1\n",
    "            tempsum.append(tempsum[flag-1] + item * (idx - stack[flag-1][1]))\n",
    "            stack.append((item, idx))\n",
    "            flag += 1\n",
    "            rightsum[idx] = tempsum[flag-1]\n",
    "            ans = max(ans, leftsum[numlen-1-idx] + rightsum[idx] - maxHeights[numlen-1-idx])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "      def makeDp(seq: List[int]) -> List[int]:\n",
    "          n = len(seq)\n",
    "          minRange = getRange(seq)\n",
    "          dp = [0] * (n + 1)\n",
    "          for i in range(n):\n",
    "              cur = seq[i]\n",
    "              j = minRange[i][0]\n",
    "              dp[i + 1] = dp[j] + (i - j + 1) * cur\n",
    "          return dp\n",
    "\n",
    "      n = len(maxHeights)\n",
    "      pre, suf = makeDp(maxHeights[:]), makeDp(maxHeights[::-1])[::-1]\n",
    "      return max(pre[i] + suf[i] for i in range(n))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def getRange(\n",
    "  nums: List[int],\n",
    "  isMax=False,\n",
    "  isLeftStrict=True,\n",
    "  isRightStrict=False,\n",
    ") -> List[Tuple[int, int]]:\n",
    "  \"\"\"\n",
    "  求每个元素作为最值的影响范围(区间)\n",
    "  默认为每个数作为左严格右非严格最小值的影响区间 [left,right]\n",
    "\n",
    "  有时候为了避免重复计算，我们可以考虑左侧`严格小于`当前元素的最近元素位置，\n",
    "  以及右侧`小于等于`当前元素的最近元素位置。\n",
    "  \"\"\"\n",
    "\n",
    "  def compareLeft(stackValue: int, curValue: int) -> bool:\n",
    "      if isLeftStrict and isMax:\n",
    "          return stackValue <= curValue\n",
    "      elif isLeftStrict and not isMax:\n",
    "          return stackValue >= curValue\n",
    "      elif not isLeftStrict and isMax:\n",
    "          return stackValue < curValue\n",
    "      else:\n",
    "          return stackValue > curValue\n",
    "\n",
    "  def compareRight(stackValue: int, curValue: int) -> bool:\n",
    "      if isRightStrict and isMax:\n",
    "          return stackValue <= curValue\n",
    "      elif isRightStrict and not isMax:\n",
    "          return stackValue >= curValue\n",
    "      elif not isRightStrict and isMax:\n",
    "          return stackValue < curValue\n",
    "      else:\n",
    "          return stackValue > curValue\n",
    "\n",
    "  n = len(nums)\n",
    "  leftMost = [0] * n\n",
    "  rightMost = [n - 1] * n\n",
    "\n",
    "  stack = []\n",
    "  for i in range(n):\n",
    "      while stack and compareRight(nums[stack[-1]], nums[i]):\n",
    "          rightMost[stack.pop()] = i - 1\n",
    "      stack.append(i)\n",
    "\n",
    "  stack = []\n",
    "  for i in range(n - 1, -1, -1):\n",
    "      while stack and compareLeft(nums[stack[-1]], nums[i]):\n",
    "          leftMost[stack.pop()] = i + 1\n",
    "      stack.append(i)\n",
    "\n",
    "  return list(zip(leftMost, rightMost))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        # 该栈是单调递增栈\n",
    "\n",
    "        n = len(maxHeights)\n",
    "        s = [(0, 0)]        \n",
    "        left = [0] * (n+1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            if maxHeights[i-1] >= s[-1][0]:\n",
    "                left[i] = left[i-1] + maxHeights[i-1]\n",
    "                \n",
    "            else:\n",
    "                while maxHeights[i-1] < s[-1][0]:\n",
    "                    s.pop()\n",
    "                left[i] = left[s[-1][1]] + (i - s[-1][1]) * maxHeights[i-1]\n",
    "            s.append((maxHeights[i-1], i))\n",
    "            \n",
    "        \n",
    "        s = [(0, n)]\n",
    "        right = [0] * (n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if maxHeights[i] >= s[-1][0]:\n",
    "                right[i] = right[i+1] + maxHeights[i]\n",
    "            else:\n",
    "                while maxHeights[i] < s[-1][0]:\n",
    "                    s.pop()\n",
    "                right[i] = right[s[-1][1]] + (s[-1][1] - i) * maxHeights[i]\n",
    "            s.append((maxHeights[i], i))\n",
    "        \n",
    "        print(left)\n",
    "        print(right)\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            ans = max(ans, left[i]+right[i-1]-maxHeights[i-1])\n",
    "\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
